package leetcode.hot100;

import datastruct.tree.TreeNode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution297 {

    public static void main(String[] args) {
        Solution297 s = new Solution297();
        TreeNode root = s.deserialize("1,2,null,null,3,4,null,null,5,null,null");
        System.out.println(s.serialize(root));
    }

    // Encodes a datastruct to a single string.
    public String serialize(TreeNode root) {
        //扩展先序遍历：把节点的null也遍历到, val1+","+val2+","+...
        StringBuilder sb = new StringBuilder();
        extendPreOrderSerialize(root,sb);
        return sb.toString();
    }

    public void extendPreOrderSerialize(TreeNode root, StringBuilder sb){
        if(root==null) sb.append("null,");
        else {
            sb.append(root.val);
            sb.append(",");
            extendPreOrderSerialize(root.left,sb);
            extendPreOrderSerialize(root.right,sb);
        }
    }

    // Decodes your encoded data to datastruct.
    public TreeNode deserialize(String data) {
        String[] vals = data.split(",");
        Queue<String> queue = new LinkedList<>(Arrays.asList(vals));
        return extendPreOrderDeserialize(vals,queue);
    }


    public TreeNode extendPreOrderDeserialize(String[] vals,Queue<String> queue){
        String curNode = queue.poll();
        if("null".equals(curNode)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(curNode));
        root.left = extendPreOrderDeserialize(vals,queue);
        root.right = extendPreOrderDeserialize(vals,queue);
        return root;
    }
}
